package org.lyc.lanqiao.bank;

import java.util.*;

/**
 * 发现环
 * https://www.lanqiao.cn/problems/108/learning/?page=1&first_category_id=1&second_category_id=3&difficulty=30
 *
 * @author Liu Yicong
 * @date 2024/3/5
 */
public class IFindRing {
	public static void main(String[] args) {
		//构建邻接矩阵构成的图
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int[][] g = new int[n + 1][n + 1]; // 图, g[1]表示与节点1相连的节点的集合, 同理g[2]表示与节点2相连的节点的集合
		for (int i = 1; i <= n; i++) {
			int start = scan.nextInt();
			int end = scan.nextInt();
			g[start][end] = 1;
			g[end][start] = 1;
		}
		scan.close();

		topologyFindRing(g, n);
	}

	/**
	 * 使用入度的拓扑排序的方法来实现
	 *
	 * @param g 图的邻接表
	 * @param n 节点数量
	 */
	public static void topologyFindRing(int[][] g, int n) {
		int[] degree = new int[n + 1]; // 存储对应节点的入度
		Queue<Integer> topologyOrderQueue = new LinkedList<>(); //用于拓扑排序的队列
		Set<Integer> result = new HashSet<>(); //用于存放最后的结果,即环路中的节点
		//初始化节点的入度
		for (int i = 1; i <= n; i++) {
			int count = 0;
			for (int j = 1; j <= n; j++) {
				if (g[i][j] == 1) count++;
			}
			degree[i] = count;
		}

		//入度为1的节点进入队列, 入度为1表示这个节点是一个孤立的单边节点, 不可能是环的一部分
		for (int i = 1; i <= n; i++) {
			if (degree[i] == 1) {
				topologyOrderQueue.add(i);
			}
		}
		/*
		删除这个孤立的单边节点, 即将这个单边节点的邻居的入度都减去1
		如果邻居在删掉这个单边节点之后入度也为1, 那么就进入队列, 依次循环, 直到删除掉所有的单边孤立节点.
		遍历结束后所有的非环内节点的入度都为1, 环内节点的入度为2
		这个步骤是按照拓扑排序的顺序, 逐步删除图中的环外节点, 那么剩余的就是环本身了
		 */
		while (!topologyOrderQueue.isEmpty()) {
			Integer poll = topologyOrderQueue.poll(); // 弹出队头元素
			for (int i = 1; i <= n; i++) { // 遍历与队头元素节点相连的节点
				if (g[poll][i] == 1) { //如果与队头元素的节点相连, 那么这个节点的度数就减一
					degree[i]--;
					if (degree[i] == 1) { //如果这个相邻节点的度数为1, 就进入队列
						topologyOrderQueue.add(i);
					}
				}
			}
		}
		for (int i = 1; i <= n; i++) {
			if (degree[i] == 2) {
				result.add(i);
			}
		}
		result.stream().sorted(Integer::compareTo).forEach(s -> System.out.print(s + " "));
	}


	/**
	 * 使用DFS算法的方式来找环,  已经证明是错误的, 例如下面的测试用例
	 * 10
	 * 8 9
	 * 4 10
	 * 1 3
	 * 2 4
	 * 1 5
	 * 3 4
	 * 1 6
	 * 1 7
	 * 2 9
	 * 5 9
	 *
	 * @param g 图的邻接表
	 * @param n 节点数量
	 */
	public static void dfsFindRing(int[][] g, int n) {
		boolean[] visited = new boolean[n + 1]; // 用于标记顶点是否被访问过
		Stack<Integer> stack = new Stack<>(); // 使用栈辅助深度优先遍历
		List<Integer> ring = new ArrayList<>();

		stack.push(1);
		visited[1] = true;

		while (!stack.isEmpty()) {
			int currentVertex = stack.pop();
			ring.add(currentVertex);
			// 遍历与当前顶点相邻的未访问过的顶点，将其入栈并标记为已访问
			for (int j = 1; j <= n; j++) {
				if (g[currentVertex][j] == 1) {
					//如果还没有遍历过, 那么就进栈
					if (!visited[j]) {
						stack.push(j);
						visited[j] = true;
					} else if (stack.contains(j)) {
						//如果已经遍历过,并且栈中仍有该节点,那么就是一个环
						ring.add(j);
						int start = n + 1;
						for (int i = 1; i <= n; i++) {
							if (g[j][i] == 1 && ring.contains(i)) {
								start = Math.min(ring.indexOf(i), start);
							}
						}
						ring = ring.subList(start, ring.size());
						stack.removeAllElements();
						break;
					}
				}

			}
		}
		ring.sort(Integer::compareTo);
		for (Integer integer : ring) {
			System.out.print(integer + " ");
		}
	}
}
